#pragma once
#include<iostream>
#include<memory>
#include<functional>
#include<vector>
#include<set>


namespace BinaryTree
{
	template<typename T>
	class Node
	{
	public:
		static std::shared_ptr<Node> create()
		{
			return std::shared_ptr<Node>(new Node());
		}
		static std::shared_ptr<Node> create(T data)
		{
			return std::shared_ptr<Node>(new Node(data));
		}
		~Node() = default;
		std::shared_ptr<Node> Get_LChild()
		{
			return LeftChild;
		}
		std::shared_ptr<Node> Get_RChild()
		{
			return RightChild;
		}
		T operator()()
		{
			return BaseData;
		}
		bool operator ==(Node node)
		{
			return BaseData == node.BaseData;
		}
		bool Add_LChild(std::shared_ptr<Node> node)
		{
			LeftChild = node;
			return true;
		}
		bool Add_RChild(std::shared_ptr<Node> node)
		{
			RightChild = node;
			return true;
		}
	private:
		Node() = default;
		Node(T data) :BaseData(data)
		{}

		T BaseData;
		std::shared_ptr<Node> LeftChild;
		std::shared_ptr<Node> RightChild;
	};
	template<typename T>
	using NodePtr = std::shared_ptr<Node<T>>;

	template<typename T>
	void PreOrderTraversal(NodePtr<T> node, std::function<void(NodePtr<T>)>func)
	{
		if (!node.use_count())
		{
			return;
		}
		func(node);
		PreOrderTraversal(node->Get_LChild(), func);
		PreOrderTraversal(node->Get_RChild(), func);
	}
	template<typename T>
	void PreOrderTraversal_NoRecursive(NodePtr<T> node, std::function<void(NodePtr<T>)>func)
	{
		if (!node.use_count())
		{
			return;
		}
		std::vector<NodePtr<T>>stack;
		stack.push_back(node);
		while (stack.size() > 0)
		{
			auto it = stack.back();
			stack.pop_back();
			func(it);
			NodePtr<T> lhs = it->Get_LChild();
			NodePtr<T> rhs = it->Get_RChild();
			if (rhs.use_count() > 0)
			{
				stack.push_back(rhs);
			}
			if (lhs.use_count() > 0)
			{
				stack.push_back(lhs);
			}
		}
	}

	template<typename T>
	void MidOrderTraversal(NodePtr<T> node, std::function<void(NodePtr<T>)>func)
	{
		if (!node.use_count())
		{
			return;
		}
		MidOrderTraversal(node->Get_LChild(), func);
		func(node);
		MidOrderTraversal(node->Get_RChild(), func);
	}
	template<typename T>
	void MidOrderTraversal_NoRecursive(NodePtr<T> node, std::function<void(NodePtr<T>)>func)
	{
		if (!node.use_count())
		{
			return;
		}
		std::vector<NodePtr<T>>stack;
		std::set<NodePtr<T>>pop_stack;
		stack.push_back(node);
		while (stack.size() > 0)
		{
			auto it = stack.back();
			auto lhs = it->Get_LChild();
			while (lhs.use_count() > 0 && pop_stack.count(lhs) == 0)
			{
				stack.push_back(lhs);
				lhs = lhs->Get_LChild();
			}
			NodePtr<T> rhs;
			do
			{
				auto back = stack.back();
				rhs = back->Get_RChild();
				func(back);
				stack.pop_back();
				if (stack.empty())
				{
					return;
				}
			} while (rhs.use_count() == 0);
			stack.push_back(rhs);
		}
	}


	template<typename T>
	void PostOrderTraversal(NodePtr<T> node, std::function<void(NodePtr<T>)>func)
	{
		if (!node.use_count())
		{
			return;
		}
		PostOrderTraversal(node->Get_LChild(), func);
		PostOrderTraversal(node->Get_RChild(), func);
		func(node);
	}
	template<typename T>
	void PostOrderTraversal_NoRecursive(NodePtr<T> node, std::function<void(NodePtr<T>)>func)
	{
		if (!node.use_count())
		{
			return;
		}
		std::vector<NodePtr<T>>stack;
		std::vector<NodePtr<T>>reverse_stack;

		stack.push_back(node);
		while (stack.size() > 0)
		{
			auto it = stack.back();
			stack.pop_back();
			reverse_stack.push_back(it);
			NodePtr<T> lhs = it->Get_LChild();
			NodePtr<T> rhs = it->Get_RChild();
			if (lhs.use_count() > 0)
			{
				stack.push_back(lhs);
			}
			if (rhs.use_count() > 0)
			{
				stack.push_back(rhs);
			}
		}
		for (int i = reverse_stack.size() - 1; i >= 0; i--)
		{
			func(reverse_stack[i]);
		}
	}
	template<typename T>
	void DepthPreTraversal(NodePtr<T> node, std::function<void(NodePtr<T>)>func)
	{
		if (!node.use_count())
		{
			return;
		}
		std::deque<NodePtr<T>>queue;

		queue.push_back(node);
		int num(1);
		do
		{
			int flag = num;
			num = 0;
			for (size_t i = 0; i < flag; i++)
			{
				auto front = queue.front();
				auto lchild = front->Get_LChild();
				auto rchild = front->Get_RChild();
				queue.pop_front();
				func(front);
				if (lchild.use_count())
				{
					queue.push_back(lchild);
					++num;
				}
				if (rchild.use_count())
				{
					queue.push_back(rchild);
					++num;
				}
			}

		} while (num > 0);

	}
	template<typename T>
	class BinaryTree
	{
	public:
		BinaryTree(NodePtr<T>node) :Root(node)
		{}
		NodePtr<T>get_root()
		{
			return Root;
		}
	private:
		NodePtr<T> Root;
	};

	void Print(NodePtr<int> node)
	{
		std::cout << (*node)() << "  ";
	}

	void BINARYTREETEST()
	{
		BinaryTree<int>tree(Node<int>::create(1));
		auto it = tree.get_root();
		it->Add_LChild(Node<int>::create(2));
		it->Add_RChild(Node<int>::create(3));
		auto it2 = it->Get_LChild();
		auto it3 = it->Get_RChild();
		it2->Add_RChild(Node<int>::create(4));
		it3->Add_LChild(Node<int>::create(7));
		auto it4 = it2->Get_RChild();
		auto it7 = it3->Get_LChild();
		it4->Add_LChild(Node<int>::create(5));
		it4->Add_RChild(Node<int>::create(6));
		it7->Add_LChild(Node<int>::create(8));
		it7->Add_RChild(Node<int>::create(9));


		it = tree.get_root();
		std::cout << std::endl << "PRE:" << std::endl;
		PreOrderTraversal<int>(it, Print);
		std::cout << std::endl << "PRE:" << std::endl;
		PreOrderTraversal_NoRecursive<int>(it, Print);
		std::cout << std::endl << "Mid:" << std::endl;
		MidOrderTraversal<int>(it, Print);
		std::cout << std::endl << "Mid:" << std::endl;
		MidOrderTraversal_NoRecursive<int>(it, Print);
		std::cout << std::endl << "Post:" << std::endl;
		PostOrderTraversal<int>(it, Print);
		std::cout << std::endl << "Post:" << std::endl;
		PostOrderTraversal_NoRecursive<int>(it, Print);
		std::cout << std::endl << "DepthPre:" << std::endl;
		DepthPreTraversal<int>(it, Print);
	}
}
